package com.agile.leetcode.easy.isCousins;

/**
 * 在二叉树中，根节点位于深度 0 处，每个深度为 k 的节点的子节点位于深度 k+1 处。
 * <p>
 * 如果二叉树的两个节点深度相同，但 父节点不同 ，则它们是一对堂兄弟节点。
 * <p>
 * 我们给出了具有唯一值的二叉树的根节点 root ，以及树中两个不同节点的值 x 和 y 。
 * <p>
 * 只有与值 x 和 y 对应的节点是堂兄弟节点时，才返回 true 。否则，返回 false。
 * <p>
 *  
 * <p>
 * 示例 1：
 * <p>
 * <p>
 * 输入：root = [1,2,3,4], x = 4, y = 3
 * 输出：false
 * 示例 2：
 * <p>
 * <p>
 * 输入：root = [1,2,3,null,4,null,5], x = 5, y = 4
 * 输出：true
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/cousins-in-binary-tree
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @Author:ChenZhangKun
 * @Date: 2021/3/25 14:17
 */
public class IsCousins {
    public static void main(String[] args) {
        IsCousins cousins = new IsCousins();

        // 查看x或y的深度
        TreeNode treeNode5 = new TreeNode(5, null, null);
        TreeNode treeNode4 = new TreeNode(4, null, null);
        TreeNode treeNode2 = new TreeNode(2, treeNode4, null);
        TreeNode treeNode3 = new TreeNode(3, null, treeNode5);
        TreeNode treeNode1 = new TreeNode(1, treeNode2, treeNode3);
        Result high = cousins.getHigh(treeNode1, 2, new Result(), 1);
        System.out.println(high);
    }

    public boolean isCousins(TreeNode root, int x, int y) {
        if (root == null) return false;
        // 拿到result
        Result high = getHigh(root, x, new Result(), 1);
        Result high1 = getHigh(root, y, new Result(), 1);
        if (high.getHigh() == high1.getHigh() && high.getParent() != high1.getParent()) {
            return true;
        }
        return false;
    }

    public Result getHigh(TreeNode root, int x, Result result, int high) {
        if (root == null) return new Result();
        if (root.left != null && root.left.val == x) {
            result.high = ++high;
            result.parent = root.val;
            return result;
        } else if (root.right != null && root.right.val == x) {
            result.high = ++high;
            result.parent = root.val;
            return result;
        } else {
            getHigh(root.left, x, result, ++high);
            high = 1;
            getHigh(root.right, x, result, ++high);
        }
        return result;
    }

    int xParent;
    int yParent;
    int xDep;
    int yDep;

    /**
     * 深度递归搜索
     *
     * @param root
     * @param dep
     * @param x
     * @param y
     * @param parent
     */
    public void dfs(TreeNode root, int dep, int x, int y, int parent) {
        if (root == null) return;
        if (root.val == x) {
            xDep = dep;
            xParent = parent;
        } else if (root.val == y) {
            yDep = dep;
            yParent = parent;
        } else {
            dfs(root.left, dep + 1, x, y, root.val);
            dfs(root.right, dep + 1, x, y, root.val);
        }

    }
}

class Result {
    int high;
    int parent;

    public int getHigh() {
        return high;
    }

    public void setHigh(int high) {
        this.high = high;
    }

    public int getParent() {
        return parent;
    }

    public void setParent(int parent) {
        this.parent = parent;
    }

    @Override
    public String toString() {
        return "Result{" +
                "high=" + high +
                ", parent=" + parent +
                '}';
    }
}

class TreeNode {
    int val;
    TreeNode left;
    TreeNode right;

    public TreeNode(int val) {
        this.val = val;
    }

    public TreeNode(int val, TreeNode left, TreeNode right) {
        this.val = val;
        this.left = left;
        this.right = right;
    }

    public TreeNode() {
    }
}
